public class MagicalString {

    public int magicalString(int n) {
        if (n <= 3) return 1;
        int[] nums = new int[n];
        nums[0] = 1;
        nums[1] = 2;
        nums[2] = 2;
        int ans = 1;
        int l = 1;
        int r = 3;
        boolean flag = true;
        while (r < n) {
            if (flag) {
                for (int i = 0; i < nums[l + 1] && r < n; i++) {
                    nums[r++] = 1;
                    ++ans;
                }
            } else {
                for (int i = 0; i < nums[l + 1] && r < n; i++) {
                    nums[r++] = 2;
                }
            }
            ++l;
            flag = !flag;
        }
        return ans;
    }
}
